package com.wayne.leetcode.problems;

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution739 {
  public static int[] dailyTemperatures(int[] temperatures) {
    Deque<Integer> stack = new ArrayDeque<>();
    int[] res = new int[temperatures.length];

    for (int i = 0; i < temperatures.length; i++) {
      int temperature = temperatures[i];
      while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
        Integer pre = stack.pop();
        res[pre] = i - pre;
      }
      stack.push(i);
    }
    return res;
  }

  public static void main(String[] args) {
    System.out.println(dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73}));
  }
}